package jianzhi_offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author: zhouyang
 * @descrpition:
 * @time: 2019-04-16 23:34
 */
public class _63_滑动窗口的最大值 {
    public static void main(String[] args) {
        _63_滑动窗口的最大值 test = new _63_滑动窗口的最大值();
        Object obj = test.maxInWindows(new int[]{2,3,4,2,6,2,5,1},3);
    }
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<>();
        if(size > num.length || num.length == 0 || size == 0) return res;
        LinkedList<Integer> queue = new LinkedList<>();
        int index = 0;
        while(index < size){
            while (!queue.isEmpty() && num[index] > num[queue.peekLast()]) queue.pollLast();
            queue.offerLast(index);
            ++index;
        }
        res.add(num[queue.peekFirst()]);
        while(index < num.length){
            while(!queue.isEmpty() && queue.peekFirst() <= index-size) queue.pollFirst();
            while (!queue.isEmpty() && num[index] > num[queue.peekLast()]) queue.pollLast();
            queue.offerLast(index);
            res.add(num[queue.peekFirst()]);
            ++index;
        }
        return res;
    }
}
